//
// Created by 紫霄 on 2020/4/9.
//
#include <stack>
using namespace std;
#ifndef LEETCODE_08TWOSTACKISUSEDTOIMPLEMENTQUEUE_H
#define LEETCODE_08TWOSTACKISUSEDTOIMPLEMENTQUEUE_H

//// 利用两个栈来构造队列； 第一种思路：
// a表示队列中的元素，想要添加的话，要把a
// 逐个压入b，这样，在b添加新元素，再重新压回a；

// class CQueue {
// public:
//  stack<int> a;
//  stack<int> b;
//
//  CQueue() {}
//
//  void appendTail(int value) {
//    int sz = a.size();
//    if (sz) {
//      for (int i = 0; i < sz; ++i) {
//        b.push(a.top());
//        a.pop();
//      }
//    }
//    b.push(value);
//    for (int i = 0; i < sz + 1; ++i) {
//      a.push(b.top());
//      b.pop();
//    }
//  }
//
//  int deleteHead() {
//    int sz = a.size();
//    if (sz) {
//      int temp = a.top();
//      a.pop();
//      return temp;
//    } else {
//      return -1;
//    }
//  }
//};

//优化后：

// 添加元素先添加到a，删除元素就是直接删除b的top；
//假如b 为空，则需要将a导入 b，再对b的首元素删除；

class CQueue {
public:
  stack<int> a;
  stack<int> b;

  CQueue() {}

  void appendTail(int value) { a.push(value); }

  int deleteHead() {
    if (a.empty() && b.empty()) {
      return -1;
    } else if (b.empty() && !a.empty()) {
      while (!a.empty()) {
        b.push(a.top());
        a.pop();
      }
    }
    int temp = b.top();
    b.pop();
    return temp;
  }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */
#endif // LEETCODE_08TWOSTACKISUSEDTOIMPLEMENTQUEUE_H
